Field of the Invention
The present invention generally relates to cognitive wireless telecommunication networks.
A cognitive network is a network with a cognitive process that can perceive current network conditions; and plan, decide, act on those conditions, learn from the consequences of its actions, all while following end-to-end goals. A cognition loop senses the environment, plans actions according to input from sensors and network policies, decides which scenario fits best its end-to-end goals using a reasoning engine, and finally acts on the chosen scenario. The system learns from the past (situations, plans, decisions, actions) and uses this knowledge to improve the decisions in the future.
A cognitive wireless networks is a radio network where each band of frequency is occupied by two groups of users: the primary users that form a primary network and the secondary users that form a secondary network. The primary users are supposed to have priority over the secondary users: i.e. the performance of the primary network should be protected against the traffic of the secondary network, i. e. the performance of the primary network should be guaranteed independently of the demand from the secondary network. Furthermore, the throughput and occupancy of the secondary network should vanish when the traffic load of the primary network increases. In other words the secondary users are only allowed to take the blank periods left by the primary users.
Economically, the existence of cognitive wireless networks is justified by the fact that many spectra are not fully used by their dedicated users, and therefore allowing secondary user access will give the opportunity to fully use the bandwidths and provide more spectrum to users. This is particularly true when part of the bandwidth is reserved for applications that have not yet been developed. The time necessary for such applications to come on to market may be long or may simply never occur (due to reasons other than technological), and precious bandwidth may simply be wasted for a substantially long period. Therefore the Federal Communication Commission has decided that any bandwidth dedicated to a new usage should also accept secondary users in the context of cognitive networks.
The problem is that the protocol used by the primary users, hereafter called the primary protocol, has in general a design that does not take into account the secondary users. In consequence the secondary protocol is sometimes harder and more costly to design than the primary protocol. Indeed the secondary users would need to be aware of the main elements of the protocol of the primary users in order to knowledgeably give priority to the later. The technological burden is thus on the secondary users while the market domination is guaranteed to the primary protocols. The result is that the spectrum may not be efficiently used and the initial goal of cognitive regulation will not be fulfilled in economic terms.
An alternative approach consists in identifying an already standardized protocol for the secondary users, for example the IEEE 802.11 standards, and then giving the burden of designing a primary protocol that naturally preempt the secondary protocol. Pre-empting the IEEE 802.11 standard is not difficult: it suffices to define a primary protocol with smaller distributed inter-frame spaces (DIFS). With this strategy the advantages are:
1) The success to market of the secondary protocol is guaranteed, since the secondary protocol is already available; therefore the spectrum is immediately fully used.
2) The technological investment for the primary protocol is guaranteed by its enforced priority over the secondary protocol.
We will consider a strategy where the sharing rules are mostly implemented in the primary network. Usually the secondary network encompasses mechanisms which allow this network to resume its transmission if the primary network is not using the channel.
We will consider a secondary network that uses the IEEE 802.11 decentralized MAC scheme. The key is a preemptive access implemented in the primary network. When both networks coexist, the secondary network captures the bandwidth when there is no activity in the primary network and in a given area (or if there is even no network nodes at all). The secondary network can use the bandwidth without any modification to its normal mode of operation.
In such a cognitive radio network, we can distinguish two different issues:
1) The first issue is sensing, which is a key feature in cognitive radio networks since it allows the secondary network to be aware of the existence of primary nodes within a given area.
2) The other issue is medium access, which is also a central issue since smart access techniques can be used by cognitive radio networks to efficiently share the medium.
Description of the Prior Art
For instance the article “Priority and Collision Detection with Active Signaling—The Channel Access Mechanism of HIPERLAN” by Philippe Jacquet, Pascale Minet, Paul Mühlethaler and Nicolas Rivierre, in Wireless personal communication 1997, http://www.springerlink.com/content/n34103q456885g51/ describes a known method for priority and collision detection with active signaling in a HIPERLAN network. In this known method, the active signaling consists, for each node wanting to access the medium, to transmit an access pattern of non-data signals in preamble to each data packet transmission attempt. This access pattern basically consists into an alternation of two listen periods separated by one signal period, these periods having various lengths. The signal transmitted in pattern signal period contains no data at all.
The procedure of collision detection and conflict resolution is performed during the access pattern preamble. The rule is that when a node, in one of its pattern listen periods, detects some energy from another node, then it immediately aborts its own access pattern preamble, and defers its packet transmission for a next attempt. Otherwise the node transmits its packet at the end of the access pattern transmission.
When a transmission attempt starts, each node in competition selects a new access pattern with the objective of having it different of the other ones. The access patterns are also functions of access priority assigned to the packet by upper level MAC data transfer services. Clearly if two nodes have two different access patterns, then the listen and signal periods, and the eventual packet transmission periods will not coincide. Therefore, providing all the nodes start access pattern preambles at the same time, one of the nodes in listen period will necessarily be the first to detect energy from another node and will defer in order to let the latter transmit its packet safely.
This is collision detection, but since it is performed before the packet, packet transmission is safe. One says that the nodes have been separated by their patterns.
The node that has priority to transmit its packet is the one holding the pattern which presents the largest digital number expanded in binary, if a pattern time slot is coded with a “1” when it is in a transmit time slot, and a “0” when it is in a listen time slot. Synchronization of pattern preambles is obtained by forcing each pattern to start after the end of frame of the last transmitted packet on the channel.
The pattern selection is such that patterns applied for high priority packets is always greater than patterns applied to lower priority packets.
As mentioned above, an interesting option for a cognitive wireless network is a secondary network according to IEEE 802.11 (WiFi).
FIG. 1 represents an exemplary burst of data packets in a classical secondary network based on the IEEE 802.11 decentralized medium access scheme. It performs the carrier sense during a random time interval. It uses a backoff i. e. a time interval used to space out repeated retransmissions of a same packet of data: The end of the transmission of a packet A by a first node of the secondary network is followed by a short interframe space SIFS and then an acknowledgement packet ack, for point-to-point packets.
After the acknowledgement packet ack, the other nodes which are waiting to transmit a packet must wait for a distributed interframe space DISF to start decrementing their backoff. This mechanism requires that the duration of a SIFS is smaller than the duration of a DISF. With this condition, the backoff is not decremented between a packet and its acknowledgement. The timing of the backoff procedure follows a time unit called “slot”, same duration as a DIFS. Any node which has pending data packets waits during the distributed inter-frame space DIFS. After the end of the distributed inter-frame space DIFS, the first node keeps waiting for a random number of slots (it decrements its backoff time). In this example it waits during four slots. After this time interval elapses, the first node sends a second packet B.
If a second node starts sending a packet before the first node has finished decrementing its backoff, the first node resumes decrementing its backoff after the end of the current transmission made by the second node.
We have an example of this situation in FIG. 1. The first node transmits a packet A. A second node has a backoff of four slots before it transmits a packet B.
Thus the second node sends its packet B after the end of the packet A transmitted by the first node (including the acknowledgement for point-to-point packets) and after waiting for four slots.
A third node transmits its packet C after an initial backoff of six slots. Thus the third node waits for the end of the second station's transmission and waits for its two remaining slots before sending its packet C.
A fourth node had an initial backoff of nine slots. Thus the fourth node waits for the end of the third station's transmission and then waits for its three remaining slots before sending its packet D.
FIG. 2 represents an exemplary burst of data packets in a classical secondary network using a generalized carrier sense multiple access technique with active signaling, which is the original basis of the known protocol HiPERLAN type 1. Rather than performing the carrier sense during a random time interval, it consists in allowing the protocol to switch between periods of signaling transmission and periods of sensing, during the signaling period. The fundamental rule of carrier sense medium access remains the same: as soon as the sensed energy is above a given threshold, then the node quits the selection process and waits for the end of the current transmission of a data packet to start competing again.
A simple way to describe the node's activity during the signaling period is to code the signaling period with “1” or “0”: 1 represents a transmission interval and “0” a sensing interval. Thus the signaling burst “101” is composed of a transmission period, a sensing period and another signaling period.
The interframe between a packet and its acknowledgement ack is still a short interframe space SISF but the time interval between the end of the acknowledgement ack and the beginning of the active signaling part is called a burst interframe space BIFS. We assume that every node always uses the same binary sequence during its signaling period, to govern its access, and we call this sequence the node access sequence.
On FIG. 2, the transmission of a packet E is followed by a short interframe space SIFS, then an acknowledgement ack, and then a burst interframe space BIFS. Then an active signaling burst is sent before sending a packet F. This active signaling burst can be represented by the binary sequence “111001110000110” in this example. The transmission of the packet F is followed by a short interframe space SIFS, and then an acknowledgement ack.
The sensing rule is such that the node with the highest binary sequence is selected for transmission. Then the second highest binary sequence is selected and so on. Of course the nodes with larger access sequences would have more access opportunities than nodes with smaller access sequence. To cope with this fairness issue, we can add the following rule: the same node must observe an idle interval of at least one large burst interframe space LBIFS, to be allowed to start its signaling phase.
In order to preserve the priority of the primary network over the secondary network, the duration of the large burst interframe space LBIFS must be chosen smaller than the duration of the distributed interframe space DIFS. The duration of the large burst interframe space LBIFS should also be larger than the duration of burst interframe space BIFS. This implies that nodes even with smaller access sequence than the access sequence used by node currently transmitting a data packet will have opportunities to send their packets. This mechanism creates “epochs”, two successive epochs being separated by an idle period with duration of at least one burst interframe space BIFS.
A possible solution to obtain a fair access is to draw the binary sequences, used in the primary network, as predetermined fixed sequences. In this case the user must not attempt to access the network before all the other contending nodes have sent their packets. So there will be timing constraints to insure that the secondary network nodes only get access to the channel when the primary network nodes have no traffic to send. The first constraint is that the BIFS is smaller than the distributed interframe space DIFS. This gives a prioritized access to the primary network nodes.
Moreover, to insure that a burst interframe space BIFS followed by listening bursts can not be interpreted as a distributed interframe space DIFS, it is sufficient that the duration of the burst interframe space BIFS plus the duration of the beginning of listening bursts at the head of the binary sequence is smaller than the duration of the DIFS. If we satisfy this constraint, the generalized carrier sense multiple access technique used for the primary network will preempt the access of a secondary user using the decentralized IEEE 802.11 MAC protocol.
However another constraint is necessary to ensure that the secondary network cannot insert transmissions in the signaling period of the primary network: The binary sequence used in the primary network must not contain too many successive zeros. The duration of a sequence of listening coded by successive zeros should be shorter than a burst interframe space BIFS. In this case, the nodes using the IEEE 802.11 access scheme do not start decrementing their backoff during the sensing intervals of the signaling bursts of the primary network, and no packet of the secondary network can be inserted. The following table presents exemplary values used in the IEEE 802.11 for the SIFS, BIFS, LBIFS, and DIFS.
DurationOne signaling burst 9 μsSIFS10 μsBIFS30 μsLBIFS40 μsDIFS50 μsMini slot 5 μs
For a primary network of size N, it consists in generating each of the N access patterns as a (d, k) binary sequence. A (d, k) binary sequences contains a string of ‘0’ where 0 appears at least d times and at most k times between two successive ‘1’. For instance, d=0 and the maximum value of k can be easily computed with the duration dDIFS of the distributed interframe space of the IEEE 802.11 MAC scheme, and the duration dRX of the receive to transmit turnout time, also called mini slot:k=dDIFS/dRX, for example 5 μs
If the primary network uses the carrier sense multiple access technique with active signaling and (0; k1) binary sequence, then we are sure that during the signaling period of a primary network node there is no listening period (i.e. idle period) of length greater than dDIFS. In other words, the IEEE 802.11 access scheme cannot start decrementing its backoff in the signaling period of the primary network, and thus no transmission can be inserted in the active signaling period of the primary network. So the primary users should transmit preamble patterns comprising a sequence of signaling burst chosen so that:                1. The signaling bursts are separated by less than the WiFi distributed inter-frame space (DIFS) time interval, in order to predate WiFi access. Indeed DIFS is the minimal time interval a WiFi node must sense the channel idle before initiating a transmission.        2. The sequence of signaling bursts identifies the primary user in order to prevent collisions.        
The terminal that transmits the lexicographically highest sequence is the winner of the contention.
Assuming that a primary user can detect an idle period of length equal to the distributed Interframe space DIFS divided by some integer k, that we will call micro-slot. For instance we suppose k=10. Therefore there are k different possible positions for the first signaling burst. The signaling burst with no micro-slot before it is lexicographically the highest. Assuming n contenders, the average number of users actually transmitting their first signaling burst is equal to:
      1    +                  (                  n          -          1                )            /      2        kwhen the two above mentioned conditions are satisfied.
The number of users transmitting their second signaling burst is equal to:
            1      +                        (                      n            -            1                    )                /        2                    k              2        ⁢                                        ⁢      etc    .  
A computation shows that the theoretical minimal length of the (d, k) sequence needed to encode N distinct access sequences (i. e. uniqueness of each preamble sequence), according to this second possible solution, is equal to log N in order to guarantee a collision free access for a primary network of size N.
FIG. 3 represents graphs of the average number of users simultaneously transmitting their ith signaling burst, for i=1 to 6, from left to right, versus the number of users (10x), on logarithmic scales, when each of the patterns is chosen as a (d, k) binary sequence, and so that all the patterns satisfy the two above mentioned conditions.
These graphs show that, according to this possible solution, the average number of users simultaneously transmitting their ith signaling burst is growing rapidly with the number of transmitters. According to this prior art solution, sorting users in a primary network of size N would require sequences with log N signaling bursts which is good as long as N is not huge.
The drawback of this prior art solution is the number of users that will simultaneously transmit their signaling bursts along with the winner. Indeed when the network is congested, this number is of order N. It means that the burst transmission per packet would require a cumulated quantity of extra energy N times larger than the transmission of the packet itself. In other words, a user must expect to transmit N sequences in average before being the winner of the contention. If N is large (e.g. 1,000,000) this is unacceptable in terms of energy (up to an extra 60 dB margin).
Another drawback of this possible solution is that, by broadcasting bursts which are, by accumulation, N times more energetic than a packet transmission itself, it would create an interference radius far much larger than the typical range of the network. With a one million user network, this would increase the interference radius by a factor 1000 and create inacceptable long range disruptions.
Furthermore the uniqueness of the preamble sequence requires the need of a central management which can be complex.
The article by PHILIPPE JACQUET ET AL: “Cognitive networks: A new access scheme which introduces a Darwinian approach”, WIRELESS DAYS (WD), 2012 IFIP, IEEE, 21 Nov. 2012 (2012-11-21), pages 1-6, XP032298475 describes a method for choosing the sequence of bursts of an access pattern, comprising the steps of computing a random integer X, and then generating a sequence of bursts corresponding to the computed random integer X.
Thanks to the steps of computing a random integer X, and then generating a sequence of bursts corresponding to the computed random integer X, the number of distinct sequences is much reduced. There may be a few identical sequences, but it is better to allow a few collisions to occur and to resolve them by retransmitting, rather than using N distinct sequences which lead to a large overhead, if a large number of sequences is needed.
The objective of the present invention is to provide an improved method to determine the random number X, so that the average energy cost E of a successful data packet transmission is below a targeted threshold.
Let us consider a given ratio k between the distributed interframe space DISF and the minislot. So k is the base for encoding X: 0, 1, . . . , k−1 to get a (0, k−1) sequence.
And let us consider a given number L of bursts in an access preamble pattern.
Without loss of generality, we can consider that the parameter X is generated by a given distribution of integers between 0 and kL−1, or by large from 0 to infinity and then truncated up to kL−1; and that the preamble key is the description in base k of the number X, so that the access preamble will contain L bursts and any larger X will always give a preamble that wins over a preamble made from a smaller value of integer X.
The average number of transmitters of the last burst is smaller than or equal to:
      r    ⁡          (              n        ,        L        ,        P            )        =            n      ⁢                        ∑                      i            =            0                                i            =                                          k                L                            -              1                                      ⁢                                  ⁢                              P            ⁡                          (                              X                =                i                            )                                ⁢                                    (                              P                ⁡                                  (                                      X                    ≤                    i                                    )                                            )                                      n              -              1                                            +          nP      ⁡              (                  X          ≥                      k            L                          )            where:n is the number of actual primary users in access contention;P is the access pattern probability distribution.
Notice that r(n,L,P)−1 is larger than the probability of collision on a packet and therefore 2−r(n,L,P) is a lower bound of the probability of successful transmission.
The average number of actually transmitted bursts dedicated to transmission, per packet preamble, includes all burst transmission, in particular the burst transmitted by losers among the n contenders. This average number of actually transmitted bursts is smaller than:
      C    ⁡          (              n        ,        L        ,        P            )        =            nk      ⁢                        ∑                      i            =            1                    L                ⁢                                  ⁢                              ∑                          j              =              1                                      j              =                              k                i                                              ⁢                                          ⁢                                    P              ⁡                              (                                                                            (                                              j                        -                        1                                            )                                        ⁢                                          k                                              L                        -                        i                                                                              <                  X                  ≤                                      jk                                          L                      -                      i                                                                      )                                      ⁢                                          (                                  P                  ⁡                                      (                                          X                      ≤                                              jk                                                  L                          -                          i                                                                                      )                                                  )                                            n                -                1                                                          +          nLP      ⁡              (                  X          ≥                      k            L                          )            
The term nLP(X≧kL) expresses the fact that the contenders with X≧kL have a preamble key equal to BS(u) that is the binary k-sequence which encodes the number u, u being an integer between 0 and k−1.
Thus, if B is the energetic cost of one transmitted burst, and U is the energy cost of one single data packet transmission, then the average energy cost E(n,L,P) of a successful data packet transmission satisfies the inequality:
      E    ⁡          (              n        ,        L        ,        P            )        ≤                              C          ⁡                      (                          n              ,              L              ,              P                        )                          ⁢        B            +      U              2      -              r        ⁡                  (                      n            ,            L            ,            P                    )                    